Object oriented programming has been used extensively by developers for organizing data when writing program code. While object oriented programming has worked relatively well, the advent of multi-core computers and devices has caused significant inefficiencies. Concurrent multi-processing that is required in multi-core devices to optimize performance is not conducive to object oriented programming.
Since the majority of programs currently developed have used object oriented programming, performance in multi-core devices is less than optimal. The memory layout of an object oriented based program would ideally be very compact with all the nodes allocated contiguously. However, this is frequently not the case in large programs, which typically perform many computations, and allocate memory during those computations. The resulting nodes would then be scattered through the heap. The pointers, meanwhile, may subsequently point to locations very far away rather than to locations that are a short distance away.
In the past, this memory allocation behavior would not have been troubling, since following a memory pointer was cheap. However, over the decades processor speeds have been increasing by 60% per year and memory access speeds by 15% per year, according to some estimations. As such, early computers could follow hundreds or thousands of pointers in the time it took to do one floating point operation. Today, the opposite situation exists. That is, following a pointer that goes to memory can have a cycle time that is equivalent to hundreds if not a thousand floating point operations. Consequently, modern computer architectures have constructed complex memory hierarchies, with Level one (L1), Level two (L2) and Level three (L3) caches to mitigate the speed differential.
The situation is exacerbated by multi-core processors, which include multiple unshared caches at the L1 and L2 level and a shared L3 cache. The issue of cache management for synchronization and interference becomes a vital task, which can affect total performance in significant ways.
Memory hierarchies only work if memory references statistically tend to be local. That is, a memory address should be close to past memory addresses so that both locations will fit into some cache line. High-performance data structures are ones that support algorithms where highly local access behaviors predominate.
With object oriented programming, the memory behavior locality is purely determined by chance. Many programming languages (most notably C and C++) allow one to control the memory allocation of objects so that with enough programming effort one can gain locality. This effort is large enough that most programmers will not undertake this exercise except in critical situations. Indeed, object oriented programming and many of its programming patterns encourage the construction of programs where application data is broken up into small pieces (objects are typically a few dozen or so bytes), with the entire structure threaded together with global pointers. If these objects happen to be contiguous, then the program performs well. If not, however, then one must go to the effort to make them so.
Consequently, there are many shortcomings in the current programming methods and there is a need for a new approach to programming data structures.